package interview;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class interview_16_19 {
    public int[] pondSizes(int[][] land) {
        int m= land.length;
        int n=land[0].length;
        boolean[][] flag=new boolean[m][n];
        List<Integer> list=new LinkedList<>();
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                int size=pool(m,n,flag,land,i,j);
                if(size!=0){
                    list.add(size);
                }
            }
        }
        int[] result=new int[list.size()];
        for(int i=0;i<list.size();++i){
            result[i]=list.get(i);
        }
        Arrays.sort(result);
        return result;
    }
    public int pool(int m,int n,boolean[][] flag,int[][] land,int i,int j){
        if(i>=0&&i<m&&j>=0&&j<n&&flag[i][j]==false){
            flag[i][j]=true;
            if(land[i][j]==0){
                return 1+pool(m,n,flag,land,i+1,j)+
                        pool(m, n, flag, land, i, j+1)+
                        pool(m, n, flag, land, i, j-1)+
                        pool(m, n, flag, land, i-1, j)+
                        pool(m, n, flag, land, i+1, j+1)+
                        pool(m, n, flag, land, i+1, j-1)+
                        pool(m, n, flag, land, i-1, j+1)+
                        pool(m, n, flag, land, i-1, j-1);
            }
        }
        return 0;
    }
}
